COMMENT ⊗   VALID 00024 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00003 00002	\rm
C00011 00003	\rm
C00025 00004	\magnification =\magstephalf
C00028 00005
C00031 00006	\magnification =\magstephalf
C00033 00007	\magnification =\magstephalf
C00036 00008
C00039 00009	\magnification =\magstephalf
C00041 00010	\magnification =\magstephalf
C00043 00011	\magnification =\magstephalf
C00045 00012	\input buslet
C00046 00013	\input buslet
C00048 00014	\input buslet
C00050 00015	\magnification =\magstephalf
C00054 00016	\rm
C00056 00017	\magnification =\magstephalf
C00058 00018	\magnification =\magstephalf
C00060 00019
C00067 00020	\magnification =\magstephalf
C00069 00021	\magnification =\magstephalf
C00071 00022	\magnification =\magstephalf
C00073 00023
C00075 00024	PUBLISHERS RECEIVING RWF 106 NOTES
C00076 ENDMK
C⊗;
\rm
\magnification=\magstephalf
\def \ip#1{\par\penalty-1000\noindent\hangindent20pt\hangafter1
\hbox to 20pt{#1\hfill}\ignorespaces}

\noindent
Computer Science 106-1

\noindent
Winter 1985

\rightline{Due: Friday, March 8, 1985}

\vskip .125in

\centerline{Assignment \#7}

\vskip .225in

This assignment is designed to give you further experience in reading and
manipulating character strings, using the functions eoln and eof, using
arrays, using procedures and using multiple files for input and output.
You may also use records and packed arrays of characters.

You are to write a program which will add together very large integer numbers.
Since these numbers may be larger than the largest integer value that PASCAL
can handle ($2↑{35}-1$ on LOTS) you will have to store the individual digits
as elements of an array.

Your program will read the names and values of variables from a value file
and the instructions to be performed from an instruction file.

The value file will contain several sets of data. Each set of data will
consist of a list of variables and their values. A variable name will
consist of 1 to 10 capital letters. Each variable has associated with it an
integer value of up to 60 digits. One variable definition will appear on
each line. The variable name will appear first, followed by one or more
spaces, followed by the value of that variable. The end of one data set
defining a set of variables will be marked by a line which contains a
single {\tt `*'} in the first column.

The instruction file will contain several sets of instructions to be
performed. Each instruction set will consist of a list of instructions.
One instruction will appear on each line. The variable name to which the
value is to be assigned will appear first followed by an equals sign
{\tt `='}. Following the equals sign will be two variable names separated by
a plus sign {\tt `+'}. There will be no blanks anywhere within the line. The
end of one instruction set will be marked by a line containing a single
star {\tt `*'}.

Note that your program must read data sets and instruction sets alternately.
You may assume that there are exactly as many instruction sets as data sets.

As an example the files containing 2 sets of data and instructions might
look like:

%insert TYPED DATA

\vfil\eject

When reading in the list of values you will need to maintain a list of
variable names read. If a variable name appearing on the left side of an
equals sign of an instruction is not already in the list of variables,
it must be added to the list.

Notice that there is nothing to mark the end of either file. Thus you must
use the EOF function to know when there are no more data or instructions
to process.

\noindent
{\it Suggestions}


\ip{1.}
You might use a record to store the name of a variable and its value.

\ip{2.}
You can use an array of such records to store the variable names and values
as they are read in and to store new variable names which appear in the
instructions. You may assume that there are no more than 20 variables in
a data set and corresponding instruction set.

\ip{3.} 
You will need a way to locate the value associated with any variable. To do
this you will need to search the array of records to find the index of
the record corresponding to the name desired. To search the array you will
need to be able to compare two strings for matching. Note that strings
can be compared if they are declared as packed arrays of characters.
Otherwise you could write your own Boolean procedure for comparing
ordinary arrays of characters.

\ip{4.}
Since you must read in the data one character at a time, you will have
to read the numbers in the value file as characters. At some time,
you will have to convert them to integers so you can do addition
(you can't add two characters). Recall that the ORD function will give
you the numeric code for a character which is a digit. Thus if ch is a
character variable and i is the corresponding digit (an integer, of course),
the assignment i:=ORD(ch)-ORD(`0') will convert ch to the proper integer value.

\ip{5.}
In your output, each data set should be preceded by a heading telling which
data set it is. The names and values of the given data should be printed,
followed by the results produced by the instruction file.

\ip{6.}
You may assume that all variable names are 10 characters or less, that all
values are 60 digits or less and that no calculated result exceeds 60 digits.

Write your program and test it on some data of your own. When your program
is running correctly run it using the data and instructions in the two
input files which will be provided. The value file is 106:VAL.DAT and
the instruction file is 106:INSTR.DAT.

Hand in a copy of your program together with the output using the above
input files.

\vfil\end
\rm

\noindent
CS154

\rightline{Spring 1984}    

\noindent
Prof. Robert W. Floyd    
\vskip .225in

\noindent
A ({\it non-deterministic}) $gsm$ is:    

A finite set of states, $Q=\{q↓1,q↓2,\ldots\}$;

An input alphabet, $\Sigma =\{\sigma↓1,\sigma↓2,\ldots\}$;

An output alphabet, $\Delta =\{\tau↓1,\tau↓2,\ldots\}$;

A set of start states, $S\subset Q$;

A set of final states, $F\subset Q$;

A transition relation, $\delta\subset Q\times\Sigma↑*\times\Delta↑*\times Q.$
\vskip .125in
\noindent
A {\it computation} of a gsm M is a sequence
$q↓0,x↓1,y↓1,q↓1,x↓2,y↓2,q↓2,\ldots ,x↓n,y↓n,q↓n$, where 
$\langle q↓{i-1},x↓i,y↓i,q↓i\rangle \in\delta$, $q↓0\in S$, $q↓n\in F$;
this computation has input $x↓1x↓2\cdots x↓n$,
and output $y↓1y↓2\cdots y↓n$.  The {\it input/output relation} $R↓M$ of $M$ 
is the set of pairs $\langle x,y\rangle$ 
such that for some computation of $M$, $x$ is the input 
and $y$ is the output. The {\it input/output function} $Q↓M$ of $M$ is defined by
$Q↓M(x)=\{y|(x,y)\in R↓M\}$.
If, for all $x$, $|Q↓M|≤1$, we may use $Q↓M(x)=$ the
$y$ (if any) such that $(x,y)\in R↓M$.
\vskip .125in
\noindent
{\sl Exercise}: Show that for every gsm, there is an equivalent one (same 
input-output relation) where if    
$\langle q,x,y,q↑\prime \rangle\in\delta$, then $|x|≤1$, $|y|≤1$.    
\vskip .125in
\noindent
Let $\hat x$ be the reverse of string $x$.  
The {\sl dual} of $M$, $\widehat M$, has transition relation  
$\{\delta↓{\widehat M}=\{\langle q↑\prime ,\hat x,\hat y,q\rangle |
\langle q,x,y,q↑\prime \rangle \in\delta↓M\}$; 
its start and final state sets are 
$S↓{\widehat M}=F↓M$ and $F↓{\widehat M}=S↓M$; $\Sigma↓{\widehat M}=\Sigma↓M$
and $\Delta↓{\widehat M}=\Delta↓M$.
\vskip .125in
\noindent
{\sl Exercise}: Show that $\langle\hat x,\hat y\rangle$ 
is in the IO relation of $\widehat M$ iff
$\langle x,y\rangle$ is in the IO relation of $M$.
\vskip .125in
\noindent
{\sl Exercise}: Show that $\skew6\widehat{\widehat M}=M$.
\vskip .125in
\noindent
The {\sl inverse} of $M$, $M↑{-1}$, has ${\Sigma↓{M↑{-1}}}=\Delta↓M$,
${\Delta↓{M↑{-1}}}=\Sigma↓M$; ${\delta↓{M↑{-1}}}
=\{\langle q,y,x,q↑\prime\rangle |\langle q,x,y,q↑\prime\rangle\in\delta↓M\}$
\vskip .125in
\noindent
{\sl Exercise}: Show that $(M↑{-1})↑{-1}=M$, and $(\widehat M)↑{-1}=
\widehat{(M↑{-1})}$.
\vskip .125in
\noindent
The {\sl composition} of two gsm's is a gsm whose IO relation is the product
of their IO relations.  To construct a gsm which is the composition 
$M↑\prime\cdot M↑{\prime\prime}$ of $M↑\prime$ and $M↑{\prime\prime}$, 
put $M↑\prime$ and $M↑{\prime\prime}$ in the form, according to the
above exercise, where all input and output strings have length $≤1$.  Let the
states of $M↑\prime\cdot M↑{\prime\prime}$ be $Q↑\prime\times Q↑{\prime\prime}$.
The transitions of $M=M↑{\prime}\cdot M↑{\prime\prime}$ include:

(1) If $\langle q↑\prime↓1,x↑\prime,a,q↑\prime↓2\rangle\in\delta↑\prime$
and $\langle q↓1↑{\prime\prime},a,x↑{\prime\prime},
q↓2↑{\prime\prime}\rangle\in\delta↑{\prime\prime}$,
then $\langle\langle q↓1↑\prime,q↓1↑{\prime\prime}\rangle ,
x↑\prime,x↑{\prime\prime},\langle q↓2↑\prime,q↓2↑{\prime\prime}\rangle\rangle  
\in\delta↓M$.

(2) If $\langle q↓1↑\prime,x,\epsilon,q↓2↑\prime\rangle \in\delta↑\prime$,
then $\langle\langle q↓1↑\prime ,q↑{\prime\prime}\rangle,
x,\epsilon,\langle q↓2↑\prime,q↑{\prime\prime}\rangle\rangle
\in\delta↓M$ for all $q↑{\prime\prime}\in Q↑{\prime\prime}$.

(3) If $\langle q↓1↑{\prime\prime},\epsilon , x,q↓2↑{\prime\prime}\rangle 
\in\delta↑{\prime\prime}$,
then $\langle\langle q↑\prime,q↓1↑{\prime\prime}\rangle,\epsilon,x,\langle q↑\prime,
q↓2↑{\prime\prime}\rangle\rangle\in\delta↓M$ for all $q↑\prime\in Q↑\prime$.
\vskip .125in
\noindent
{\sl Exercise}: define the starting and final sets of the composition, and show 
that the composition has the stated properties.
\vskip .125in
\noindent
{\sl Exercise}: 
Show$\widehat{M↑\prime\cdot M↑{\prime\prime}}≡\widehat{M↑\prime}
\cdot\widehat{M↑{\prime\prime}}$; 
$(M↑\prime\cdot M↑{\prime\prime})↑{-1}≡(M↑{\prime\prime})↑{-1}\cdot 
(M↑\prime)↑{-1}$; $(M↓1\cdot M↓2)\cdot M↓3≡M↓1\cdot(M↓2\cdot M↓3)$.
\vskip .125in
\noindent
If $1↓\Sigma$ is the machine whose IO relation is the identity relation on
$\Sigma↑*$, show $1↓\Sigma\cdot M≡M\cdot 1↓\Sigma ≡M$.  
That is, composition of gsm's (with a given alphabet for both input and output)
is a {\sl semigroup} with $1↓\Sigma$ as the identity (i.e., a {\sl monoid}).
\vskip .125in
\noindent
A finite automaton {\sl acceptor} is a gsm without output; every element of $\delta$
is of the form $\langle q↓1,x,\epsilon,q↓2\rangle$.
\vskip .25in
\noindent
\sevenrm{gsms.tex[1,rfn]}

\par\vfil\eject

\rm
\noindent
Composition of a gsm with an FA yields an FA.  The IO relation of an FA is
$R\times\{\epsilon\}$, for any regular set $R$.  The inverse of such an FA is
a {\sl generator} for the regular set $R$; it reads nothing and writes an
arbitrary member of $R$.
\vskip .125in
\noindent
A {\sl filter} is an automaton whose transitions are all of the form
$\langle q↓1,x,x,q↓2\rangle$; its IO relation is a subset of the identity relation.  
A gsm filter passes through the members of any regular set you choose, 
and rejects all other input.
\vskip .125in
\noindent
To show that the intersection of two regular sets $R↓1$, $R↓2$ is regular, construct
a filter $M↓1$ for $R↓1$ and an FA $M↓2$ for $R↓2$; then $M↓1\cdot M↓2$ is an
FA for $R↓1∩R↓2$.
\vskip .125in
\noindent
To show that regular sets are closed under gsm mappings, let $M↓1$ generate a
regular set $R$, and $M↓2$ be any gsm; then $M↓1\cdot M↓2$ generates the
$M↓2$-mapping of $R$, and its inverse is an FA accepting the $M↓2$-mapping of $R$.
\vskip .125in
\noindent
To show regular sets closed under inverse gsm mappings, we just notice that the
inverse of a gsm mapping is itself a gsm mapping.
\vskip .125in
\noindent
The projections of the I/O relation of a gsm (the {\sl domain} and {\sl range})
are clearly regular sets.
\vskip .125in
\noindent
If $C$ is any class of automata characterized by a set of allowed devices (e.g.
having one stack, or having a finite number of counters), then $C$ is closed under
composition on either side with gsm's, using the natural defintition of composition. 
E.g., let $C$ be the class of NPDA's; by composition with a filter for a regular
set, we find that the intersection of a regular set with a CFL is a regular set.
By using a NPDA generator for a CFL, and composing it with a gsm, we find
that the CFL's are closed under gsm mappings and inverse gsm mappings.  We
similarly find that a PDA transducer maps a regular set into a CFL.
\vskip .125in
\noindent
{\it Theorem}: Every automaton is equivalent to a composition of gsm's and unit
automata, where a unit automaton has one device.
\vskip .125in
\noindent
Proof: Let $M↓1$ be the automaton.  Let $M↓2$ be a gsm which generates 
sequences of transitions for $M↓1$, while reading the inputs of those transitions.
Let $M↓3$, $M↓4,\ldots$, $M↓n$ be filters for the devices used by $M↓1$.  
Let $M↓{n+1}$ be an automaton that reads transitions of $M↓1$, while writing 
their outputs.  Then $M↓2\cdot M↓3\cdots M↓{n+1}≡M↓1$.
\vskip .125in
\noindent
{\it Theorem}: Every recursively enumerable set is a projection of the 
intersection of two CFL's.
\vskip .125in
\noindent
Proof: Let $M↓0$ be a Turing machine generating the set.  Let $M↓1$ be an equivalent
two-stack machine. The previous construction gives $M↓1\cdot M↓2\cdot M↓3\cdot M↓4$,
where $M↓1$ is a gsm generator, and $M↓2$ is a PDA filter, so $M↓1\cdot M↓2$
generates a CFL; $M↓3$ filters a CFL, so $M↓1\cdot M↓2\cdot M↓3$ generates
the intersection of two CFL's.  $M↓4$ is a projection gsm.  QED.
\vskip .125in
\noindent
A gsm is deterministic if inputs uniquely determine transitions.
Construction of compositions can be twiddled to preserve
determinism.  A deterministic gsm has an input/output function.
\vskip .125in
\noindent
The {\it null\/} gsm $\emptyset$ has one state, $q↓0\notin F$, and no arcs.  Under
composition, $\emptyset \cdot M≡M\cdot\emptyset ≡\emptyset$, 
where equivalence of gsm's means having the same I/O relation.
\vskip .225in
\noindent
We readily define $M↓1+M↓2$, $M↑*$, and $M↑+$. Define $M↓{\epsilon}$ with one state 
$q↓0\in F$, and no transitions.  Then $\emptyset +M≡M+\emptyset ≡M$, 
$\emptyset ↑*≡M↓\epsilon$,
$\emptyset ↑+≡\emptyset$, $1↑*↓{\Sigma}≡1↑+↓{\Sigma}≡1↓{\Sigma}$.  
Similarly, define $M↓1\otimes M↓2$ to have I/O relations 
$\{(x↓1x↓2,y↓1y↓2)|(x↓1,y↓1)\epsilon R↓{M↓1},(x↓2,y↓2)\in R↓{M↓2}\}$.
$M↓{\epsilon}\otimes M=M\otimes M↓{\epsilon}=M$.
\vskip .125in
\noindent
The results above are essential to CS154 and should be memorized.

\vfill\eject\end
\magnification =\magstephalf
\input rosmac
\def\disleft#1:#2:#3\par{\par\hangindent#1\noindent
			 \hbox to #1{#2 \hfill \hskip .1em}\ignorespaces#3\par}
\def\display#1:#2:#3\par{\par\hangindent #1 \noindent
			\hbox to #1{\hfill #2 \hskip .1em}\ignorespaces#3 \par}
\def\adx#1:#2\par{\par\halign{\hskip #1##\hfill\cr #2}\par}

\def\outlineone#1:{\par\hangindent 19pt\noindent
  \hbox to 19 pt{#1\hfill}\ignorespaces}

\roslet
\today

\vskip 30pt


\address






\body
Dear Ex-student of computer science at Stanford:

You have been out of the nest long enough to have some experience 
with the power of your wings. We are interested in your current
assessment of the usefulness of the courses you took. We enclose
a current set of course descriptions to jog your memory. Please
help us in self-assessment, by writing down the names and/or
numbers of the courses you found most useful, with the names of
the professors if possible, and a phrase or more about what made
them valuable. We suggest a best-first list (BFL). Feel free to
list any other part of your CSD education that has been helpful,
and to say what you would do differently, or ask us to do differently,
if you were doing it again.

It would also be helpful if you sketched your current work environment
and subject matter. We also enclose a short salary questionnaire,
which will be kept confidential and separate, and which will help
us advise both students and potential employers about market conditions.

\closing
%Sincerely yours,

%Robert W.~Floyd



%\annotations
%RWF/rfn
%\smallskip
%Enclosures
%\smallskip
%cc: 
%\smallskip
%\ps 
%P.S.: 
 
\endletter

\vfil\end


\magnification =\magstephalf
\input buslet
\def\disleft#1:#2:#3\par{\par\hangindent#1\noindent
			 \hbox to #1{#2 \hfill \hskip .1em}\ignorespaces#3\par}
\def\display#1:#2:#3\par{\par\hangindent #1 \noindent
			\hbox to #1{\hfill #2 \hskip .1em}\ignorespaces#3 \par}
\def\adx#1:#2\par{\par\halign{\hskip #1##\hfill\cr #2}\par}


\rwflet

\vskip 30pt
	
\address 
James DeWolf
Senior Editor
Computer Science
Addison-Wesley Publishing Co.
Sand Hill Road
Menlo Park, CA  94025			

\body
Dear Mr. DeWolf:

I enclose a table of contents for my manuscript on algorithms, programming,
and Pascal. I have sketched the major subtopics only in those sections where
the manuscript is sketchy or unwritten.

I also enclose a page addressed to the reader, explaining why there are
large gaps in the early part of the ms., and attempting to direct the
editor's or reviewer's attention away from the flaws inherent in an
incomplete book expanded from lecture notes.

I am sending separately the currently version of the manuscript, now at
248 pages.

The comments on course evaluation forms, from four students out of thirteen,
on the course notes: (roughly the current form of the ms.):

(1) Well-conceived introduction to programming. Interesting material.
The book looks like it will be good. I don't think it's quite organized yet.

(2) The text was sufficient.

(3) The lecture notes for the course is (sic) excellent.

(4) I like the handouts. They are well written and interesting to read.

Considering how fragmentary the ms.~is, I consider this high praise.

\closing
Sincerely yours,
Robert W.~Floyd 

\annotations
RWF/rfn
%\smallskip
%Enclosure
%\smallskip
%cc: Matthew Kahn
%\smallskip
%\ps
%P.S.: whatever you wish to say here

\endletter

\makelabel
\end

\magnification =\magstephalf
\input buslet
\def\disleft#1:#2:#3\par{\par\hangindent#1\noindent
			 \hbox to #1{#2 \hfill \hskip .1em}\ignorespaces#3\par}
\def\display#1:#2:#3\par{\par\hangindent #1 \noindent
			\hbox to #1{\hfill #2 \hskip .1em}\ignorespaces#3 \par}
\def\adx#1:#2\par{\par\halign{\hskip #1##\hfill\cr #2}\par}


\rwflet

\vskip 30pt
	
\address 
Karl V.~Karlstrom
Assistant Vice-President
Editor, Computer Science
and Applied Mathematics
Prentice-Hall, Inc.
Englewood Cliffs, NJ 07632

\body
Dear Karl:

I just ran across a 1979 letter from you (copy attached) and I want you to
know that your encouragement is one reason I have finally got off my rear
and done some serious writing, now in the hands of your colleague Marcia
Horton {\it inter alia}.

If you find yourself in the SF area, do call me. It would be a pleasure to
see you again.

\closing
Sincerely yours,
Robert W.~Floyd 

\annotations
RWF/rfn
%\smallskip
%Enclosure
%\smallskip
%cc: Matthew Kahn
%\smallskip
%\ps
%P.S.: whatever you wish to say here

\endletter

\makelabel
\end
\magnification =\magstephalf
\input buslet
\def\disleft#1:#2:#3\par{\par\hangindent#1\noindent
			 \hbox to #1{#2 \hfill \hskip .1em}\ignorespaces#3\par}
\def\display#1:#2:#3\par{\par\hangindent #1 \noindent
			\hbox to #1{\hfill #2 \hskip .1em}\ignorespaces#3 \par}
\def\adx#1:#2\par{\par\halign{\hskip #1##\hfill\cr #2}\par}


\rwflet

\vskip 30pt
	
\address 






\body
%Dear 

Stefan Sharkansky took my course on Sorting and Searching, out of
Knuth v.3, last winter. He had a top 95 on the takehome midterm; the
next grade was 85. On the takehome final I promised an A to anyone
who got three problems (out of nine) substantially right. There
were higher scores than his, mainly through accumulation of partial
credit, but several of his solutions were superb: elegant, motivated,
and efficient solutions to problems requiring three or four pages
of combinatorial identities, generating functions, transformations
of recurrence relations, and all that. (The higher scores were made
by a good computer science Ph.D.~student, and another M.S.~student
whom I would also enthusastically admit to our Ph.D.~program.)

He was my TA in the spring, in a formal languages and computability
course based on Hopcroft and Ullman. Although he was learning the
material at the same time, he was a very capable TA to whom I was
able to delegate much responsibility for composing and reviewing
problems and solutions.

Stefan has good mathematical instincts, and should do very well 
in the deductive side of computer science research, or in an
applied math program. I see no reason that he would not be a
credit to any Ph.D.~program.

\closing
Sincerely yours,
Robert W.~Floyd 

\annotations
RWF/rfn
%\smallskip
%Enclosure
%\smallskip
%cc: Matthew Kahn
%\smallskip
%\ps
%P.S.: whatever you wish to say here

\endletter

\makelabel
\end

\magnification =\magstephalf
\input buslet
\def\disleft#1:#2:#3\par{\par\hangindent#1\noindent
			 \hbox to #1{#2 \hfill \hskip .1em}\ignorespaces#3\par}
\def\display#1:#2:#3\par{\par\hangindent #1 \noindent
			\hbox to #1{\hfill #2 \hskip .1em}\ignorespaces#3 \par}
\def\adx#1:#2\par{\par\halign{\hskip #1##\hfill\cr #2}\par}


\rwflet

\vskip 30pt
	
\address 
Mr.~Nick J.~Patterson
Deputy Director
Communications Research Division
Institute for Defense Analysis
Thanet Road
Princeton, NJ 08540

\body
Dear Mr.~Patterson:

I have a high opinion of Richard Beigel. He was my teaching assistant, twice,
when still an undergraduate. He was as capable, energetic, and responsible
an assistant as I have had for five years, and comparable to assistants I
have had who are now full professors at major universities.

I consider his doctoral dissertation significant and imaginative, although
I am not fully qualified to pass judgment in his area.

Beigel lived in my house for a year. I am not known as easy to live with,
but I enjoyed the interaction, so I would say he has abundant resources
of sociability and tact.

Beigel has the instinct of the pure mathematician for elegance and precision
in intellectual work. I think he will be a significant contribution to
theoretical computer science, or related fields.

\closing
Sincerely yours,
Robert W.~Floyd 
Professor

\annotations
RWF/rfn
%\smallskip
%Enclosure
%\smallskip
%cc: Matthew Kahn
%\smallskip
%\ps
%P.S.: whatever you wish to say here

\endletter

\makelabel
\end
\magnification =\magstephalf
\input buslet
\def\disleft#1:#2:#3\par{\par\hangindent#1\noindent
			 \hbox to #1{#2 \hfill \hskip .1em}\ignorespaces#3\par}
\def\display#1:#2:#3\par{\par\hangindent #1 \noindent
			\hbox to #1{\hfill #2 \hskip .1em}\ignorespaces#3 \par}
\def\adx#1:#2\par{\par\halign{\hskip #1##\hfill\cr #2}\par}


\rwflet

\vskip 30pt
	
\address 






\body
%Dear 

Jay Lao has taken two of my courses: Sorting and Searching, out of
Knuth v.3, and Formal Languages, out of Hopcroft and Ullman.
In the former, a class mainly of computer science MS students,
his work was a shade below the class average, and I gave him a
B. In the latter, on both exams he ranked fifth or sixth out of
more than eighty students, which indicates to me that he is able
to do very good mathematical computer science.

Unfortunately, he is a bit shy, and I don't really know him well,
nor do I have any memory of the details of his work that would
let me make a qualitative assessment.

\closing
Sincerely yours,
Robert W.~Floyd 

\annotations
RWF/rfn
%\smallskip
%Enclosure
%\smallskip
%cc: Matthew Kahn
%\smallskip
%\ps
%P.S.: whatever you wish to say here

\endletter

\makelabel
\end
\magnification =\magstephalf
\input buslet
\def\disleft#1:#2:#3\par{\par\hangindent#1\noindent
			 \hbox to #1{#2 \hfill \hskip .1em}\ignorespaces#3\par}
\def\display#1:#2:#3\par{\par\hangindent #1 \noindent
			\hbox to #1{\hfill #2 \hskip .1em}\ignorespaces#3 \par}
\def\adx#1:#2\par{\par\halign{\hskip #1##\hfill\cr #2}\par}


\rwflet

\vskip 30pt
	
\address 
Prof.~Robert L.~Ashenhurst
ACM Forum Editor
University of Chicago
1101 E.~58th Street
Chicago, IL 60637

\body
Dear Prof.~Ashenhurst:

Tut, tut, ACM! I am not merely a ``famous person'' and Turing
award winner (CACM, Oct.~1987, p.~890). My highest distinction
is that I am a past ACM publication editor. I was an associate
editor of JACM for 1967-1969, and I edited the August 1966
special issue of CACM devoted to papers on symbolic and algebraic
manipulation, the first issue that exceeded one hundred pages of
editorial material. Assess thyself!

\closing
Sincerely yours,
Robert W.~Floyd 

\annotations
RWF/rfn
%\smallskip
%Enclosure
%\smallskip
%cc: Matthew Kahn
%\smallskip
%\ps
%P.S.: whatever you wish to say here

\endletter

\makelabel
\end
\magnification =\magstephalf
\input buslet
\def\disleft#1:#2:#3\par{\par\hangindent#1\noindent
			 \hbox to #1{#2 \hfill \hskip .1em}\ignorespaces#3\par}
\def\display#1:#2:#3\par{\par\hangindent #1 \noindent
			\hbox to #1{\hfill #2 \hskip .1em}\ignorespaces#3 \par}
\def\adx#1:#2\par{\par\halign{\hskip #1##\hfill\cr #2}\par}


\rwflet

\vskip 30pt
	
\address 
Dr.~Hans Morawa
8 M\"unchen 2 $\cdot$ Stielerstrasse 7
WEST GERMANY

\body
Dear Dr.~Morawa:

I will be happy to meet you while you are at Stanford. Because my
summer schedule is dependent on other people's plans, I can not set
a date, but I am sure we can find mutually acceptable times after
you arrive.

\closing
Sincerely yours,
Robert W.~Floyd 

\annotations
RWF/rfn
%\smallskip
%Enclosure
%\smallskip
%cc: Matthew Kahn
%\smallskip
%\ps
%P.S.: whatever you wish to say here

\endletter

\makelabel
\end
\input buslet
%another letter.file
\def \ip#1{\par\penalty-1000\noindent\hangindent20pt\hangafter1
\hbox to 20pt{#1\hfill}\ignorespaces}

\memoto  MSCS Committee

\from  Robert W. Floyd 

\subject Chuan-Chieh Ko

\body

I am attaching without any recommendation a program proposed by Mr.~Ko.
It seems to me that we should somehow broaden part (b) of the software
theory option, for example to include 335, 360, 364, 367. I don't
know enough about 441 and 442 to recommend them.

\bigskip
RWF/rfn
%\smallskip
%Enclosure: 
\smallskip
cc: Mr.~Ko
%\smallskip
%\ps
%P.S.: 

\endletter
\end

\input buslet
%another letter.file
\def \ip#1{\par\penalty-1000\noindent\hangindent20pt\hangafter1
\hbox to 20pt{#1\hfill}\ignorespaces}

\memoto  Whomever

\from  Robert W. Floyd 

\subject Courses and Degrees

\body

%Put your letter here.

Someone garbled the prerequisites of CS254. ``Familiarity'' should not be
capitalized; ``i.e.'' should be ``e.g.,'' and ``(106)'' once should have
been ``(160),'' but now should be ``(Philosophy 159).'' There should be
no comma after B. Whoever mangled my description makes me look like an
idiot, and should be shot.

\bigskip
RWF/rfn
%\smallskip
%Enclosure: U.N.\ Fellowship award letter
%\smallskip
%cc: Mary Lou Allen
%\smallskip
%\ps
%P.S.: whatever you wish to say here

\endletter
\end

\input buslet
%another letter.file
\def \ip#1{\par\penalty-1000\noindent\hangindent20pt\hangafter1
\hbox to 20pt{#1\hfill}\ignorespaces}

\memoto  Sol Feferman

\from  Robert W Floyd 

\subject Fixed point theory

\body

%Put your letter here.

Thank you. Nice ordinal proof. It can be tuned a bit more.
Let $f↓\alpha = sup \lbrace \tau \langle f↓\beta \rangle \vert \beta
< \alpha\rbrace$ for all $\alpha$, i.e. using course-of-values
induction. Then if $\alpha ↓1 ≤ \alpha ↓2$, $f↓{\alpha ↓1}$ is a
sup over a smaller index set than $f↓{\alpha ↓2}$ and
$f↓{\alpha ↓1} ≤ f↓{\alpha ↓2}$. The rest is as in your proof.

I took liberties with the conventional ordinal numbers; my
$\infty$'s are of course purely formal marks, for presentation
to people who don't know what $\omega$ is.  I know the set
theory convention, I just hate it. If $\omega\cdot$k means
``$\omega$ times k,'' then it should be the result of adding
k, $\omega$ times, or what you guys call k$\cdot\omega$.
But thanks for trying to set me straight.

\bigskip
RWF/rfn
%\smallskip
%Enclosure: U.N.\ Fellowship award letter
%\smallskip
%cc: Mary Lou Allen
%\smallskip
%\ps
%P.S.: whatever you wish to say here

\endletter
\end

\magnification =\magstephalf
\input buslet
\def\disleft#1:#2:#3\par{\par\hangindent#1\noindent
			 \hbox to #1{#2 \hfill \hskip .1em}\ignorespaces#3\par}
\def\display#1:#2:#3\par{\par\hangindent #1 \noindent
			\hbox to #1{\hfill #2 \hskip .1em}\ignorespaces#3 \par}
\def\adx#1:#2\par{\par\halign{\hskip #1##\hfill\cr #2}\par}


\rwflet

\vskip 30pt
	
\address 
Prof.~Robert E.~Tarjan
Dept.~of Computer Science
Princeton University     
Princeton, NJ 08544

\body
Dear Bob:

I hear that you have been selected for the Turing award. I only wonder
that it took them so long.

Many recipients of the award have chosen in their lecture to review
the work that led to the award. There is nothing wrong with that,
though some of the writers for {\it Science} magazine probably do it
better than most of us can do for ourselves. I chose to use my
moment in the spotlight to say what I could to change the practice
of our profession most beneficially. Minsky was another who chose
that route. Give it a thought. You may come to greater prizes, but
you may never have a better chance to preach an elegant sermon to
a respectful audience.

Among the things I am most proud of in my career are several
distinguished doctoral dissertations in which I played an
advisory part.
I find now that your generation of researchers has a level of training,
especially in mathematics, that I can't match and haven't the
stamina to keep up with. In fact, I'm looking at concentrating my
efforts on less abstract tasks: software ideas, cleaning up and
generalizing the fundamental results in computability and formal
languages. I'm glad I had something to do with setting the process
in motion.

\closing
Congratulations,
Bob

\annotations
RWF/rfn
%\smallskip
%Enclosure
%\smallskip
%cc: Matthew Kahn
%\smallskip
%\ps
%P.S.: whatever you wish to say here

\endletter

\makelabel
\end

\rm
\magnification=\magstep1
\baselineskip=24pt

Let $f(x)$ be an algebraic or transcendental function possessing
a simple zero $c$ in a finite interval $(a,b)$ of the real axis.
We assume that $f(x)$ is continuous in $\lbrack a,b\rbrack$ and
has a continuous second derivative in a neighborhood of $c$.
The authors describe a method for computing this zero numerically.
For this purpose they introduce the ordinary integral

$$J = \int ↑b↓a\lbrack (b-x)(x-a)\rbrack ↑{- {1\over 2}}\lbrack (x-c)/f(x)
\rbrack dx$$

\noindent
and use two numerical integration formulas, $J↓n↑{(1)}$ (Gauss) and
$J↓n↑{(2)}$ (Lobatto-Chebyshev) for computing $J$. They equate
these results and drop the error terms to obtain an explicit
formula for $c↓n$, an approximation to $c$. They discuss the
convergence of the method. They illustrate the effectiveness of
the method by applying it to the solution of two classical 
transcendental equations.

\vfil\end
\magnification =\magstephalf
\input buslet
\def\disleft#1:#2:#3\par{\par\hangindent#1\noindent
			 \hbox to #1{#2 \hfill \hskip .1em}\ignorespaces#3\par}
\def\display#1:#2:#3\par{\par\hangindent #1 \noindent
			\hbox to #1{\hfill #2 \hskip .1em}\ignorespaces#3 \par}
\def\adx#1:#2\par{\par\halign{\hskip #1##\hfill\cr #2}\par}


\rwflet

\vskip 30pt

\rightline{\bf CONFIDENTIAL}
	
\address 
N.J.~Lamb
Research Services Officer
University of Queensland
St.~Lucia, Queensland
AUSTRALIA 4067

\body
Dear Mr.~Lamb:

I enclose a copy of a review of the Bailes, Lister, and Weber
proposal for the Australian Research Grants Committee. My
opinions are unchanged. I am not sufficiently knowledgeable
about functional programming to assess the Bailes proposal.

\closing
Sincerely yours,
Robert W.~Floyd 

\annotations
RWF/rfn
\smallskip
Enclosure
%\smallskip
%cc: Matthew Kahn
%\smallskip
%\ps
%P.S.: whatever you wish to say here

\endletter

\makelabel
\end
\magnification =\magstephalf
\input buslet
\def\disleft#1:#2:#3\par{\par\hangindent#1\noindent
			 \hbox to #1{#2 \hfill \hskip .1em}\ignorespaces#3\par}
\def\display#1:#2:#3\par{\par\hangindent #1 \noindent
			\hbox to #1{\hfill #2 \hskip .1em}\ignorespaces#3 \par}
\def\adx#1:#2\par{\par\halign{\hskip #1##\hfill\cr #2}\par}


\rwflet

\vskip 30pt
	
\address 
Prof.~Jacques Cohen
Computer Science Department
Brandeis University
Waltham, MA 02254

\body
Dear Jacques:

Thank you for your report on the origins of Prolog. I was amazed
to learn I had so much to do with it. I know I had much contact
with Colmeraur at the time, but one does not always know how much
effect one has on other people's thought.

\closing
Sincerely yours,
Robert W.~Floyd 

\annotations
RWF/rfn
%\smallskip
%Enclosure
%\smallskip
%cc: Matthew Kahn
%\smallskip
%\ps
%P.S.: whatever you wish to say here

\endletter

\makelabel
\end

\input buslet
%another letter.file
\def \ip#1{\par\penalty-1000\noindent\hangindent20pt\hangafter1
\hbox to 20pt{#1\hfill}\ignorespaces}

\memoto  Curriculum Committee

\from  Robert W. Floyd 

\subject CS 106H

\body

%Put your letter here.

I have designed an introductory course in algorithms and programming
aimed at a high level understanding. The notions of invariant and
variant expressions pervade the course. I systematically present
such paradigms as recursion, problem size reduction, divide and
conquer, dynamic programming, branch and bound, discrete simulation.
I show why analysis of numerical error is essential in all fields
of programming, and how to do it. I show systematic diagnostic
techniques, such as use of drivers and stub procedures. I introduce
standard data structures like lists, stacks, queues, and heaps.
I exemplify with classic algorithms: Gaussian elimination as
problem size reduction, the alpha-beta algorithm as both recursion
and branch-and-bound, heapsort to show the use of nontrivial data
structures, Machin's computation of pi to illustrate analysis of
costs and accuracy.

I found that most students taking CS106 couldn't or wouldn't operate
at this level of abstraction, so I made my section an honors
section. It involved more work, but because it covered most of
the course description of what was then CS107, I believed that
many of my students were ready for CS108. It is my understanding,
though, that CS108 now requires a systematic preparation in Pascal
language features, not all of which I cover. CS106X was set up
to be a one-quarter preparation for CS108. Naturally, the most
ambitious students want to advance quickly, so they take 106X.
My enrollments have dropped from thirty to twelve to four, even
though my students have seemed satisfied with my course.

I have worked for six years on the design of this course.  I
believe in it; I think for the students who can handle it this
is the right way to start. I think the discipline of programming
in the large should come later than the first course, that there
is no point in teaching doctrines of maintenance, team programming,
etc., to students until they can do a one-person one-shot program
well. I think that algorithms should be studied independently of the
features of Pascal.

I propose that CS106 be accompanied by a 1-unit lab, meeting 1-2
hours per week by arrangement, probably run by a TA, to cover
Pascal details and to practice programming. I am open to any
alternatives that would not penalize the high-achieving student
who wants to take my course, which seems to imply that my course
must have at least an option of preparing for CS108.

I would prefer to keep the advanced Pascal details fairly separate
from the core of my course, so that the science student who wants to
study algorithms but not to be a professional hacker can keep his 
eye on the ball.

Perhaps the committee in its wisdom can help with two other problems
connected with CS106H. The title of CS106 and CS106X is Intro.~to
Software Engineering. Naturally that sounds more advanced than
Intro.~to Computer Programming. I don't want to adopt a pretentious
title, but I also don't like the connotations of the currrent
contrast in titles. Maybe ``Intro.~to Algorithms and Computer
Programming'' for CS106H?

Also, I occasionally get students who are in no way able to cope
with an honors course. I announce at the beginning what it will be
like, and what the alternatives are. Anybody have any suggestions?
Maybe CS106H should always be at the same hour as a section of
regular CS106, so there would be no schedule pressure.

In the past, I've had some unwelcome surprises, like the
introduction of C106X and the Software Engineering title of the
other courses.  I have a major investment in this course and
in the manuscript I am developing for it. I would appreciate
being kept informed about all curriculum changes that may
affect my environment.

\bigskip
RWF/rfn
%\smallskip
%Enclosure: U.N.\ Fellowship award letter
%\smallskip
%cc: Mary Lou Allen
%\smallskip
%\ps
%P.S.: whatever you wish to say here

\endletter
\end

\magnification =\magstephalf
\input buslet
\def\disleft#1:#2:#3\par{\par\hangindent#1\noindent
			 \hbox to #1{#2 \hfill \hskip .1em}\ignorespaces#3\par}
\def\display#1:#2:#3\par{\par\hangindent #1 \noindent
			\hbox to #1{\hfill #2 \hskip .1em}\ignorespaces#3 \par}
\def\adx#1:#2\par{\par\halign{\hskip #1##\hfill\cr #2}\par}


\rwflet

\vskip 30pt
	
\address 
Dr.~Jon Bentley
AT\&T Bell Labs
600 Mountain Avenue
Murray Hill, NJ 07974

\body
Dear Jon:

I will be happy to have your Pearls column on my sampling
algorithm reprinted in book form.

\closing
Sincerely yours,
Robert W.~Floyd 

\annotations
RWF/rfn
%\smallskip
%Enclosure
%\smallskip
%cc: Matthew Kahn
%\smallskip
%\ps
%P.S.: whatever you wish to say here

\endletter

\makelabel
\eject
\magnification =\magstephalf
\input buslet
\def\disleft#1:#2:#3\par{\par\hangindent#1\noindent
			 \hbox to #1{#2 \hfill \hskip .1em}\ignorespaces#3\par}
\def\display#1:#2:#3\par{\par\hangindent #1 \noindent
			\hbox to #1{\hfill #2 \hskip .1em}\ignorespaces#3 \par}
\def\adx#1:#2\par{\par\halign{\hskip #1##\hfill\cr #2}\par}


\rwflet

\vskip 30pt
	
\address 
Prof.~Ron Weber
Dept.~of Commerce
University of Queensland
St.~Lucia
Queensland
AUSTRALIA 4067

\body
Dear Prof.~Weber:

I have sent a review of your proposal, by FAX and airmail. It had
been buried under clutter on my desk. My apologies. Should you
perform the proposed research, I would be glad to comment on your
detailed plans.

\closing
Sincerely yours,
Robert W.~Floyd 

\annotations
RWF/rfn
%\smallskip
%Enclosure
%\smallskip
%cc: Matthew Kahn
%\smallskip
%\ps
%P.S.: whatever you wish to say here

\endletter

\makelabel
\end
\magnification =\magstephalf
\input buslet
\def\disleft#1:#2:#3\par{\par\hangindent#1\noindent
			 \hbox to #1{#2 \hfill \hskip .1em}\ignorespaces#3\par}
\def\display#1:#2:#3\par{\par\hangindent #1 \noindent
			\hbox to #1{\hfill #2 \hskip .1em}\ignorespaces#3 \par}
\def\adx#1:#2\par{\par\halign{\hskip #1##\hfill\cr #2}\par}


\rwflet

\vskip 30pt
	
\address 
Mr.~Mihalis Yannakakis
AT\&T Bell Labs
Room 2C-319
600 Mountain Avenue
Murray Hill, NJ 07974

\body
Dear Mr.~Yannakakis:

Last winter
Jeff Ullman wrote to you to ask your help in evaluating Assistant
Professor Ernst Mayr. I enclose copies of Jeff's letter and your
response. I hope that you can send me a current evaluation,
possibly by indicating changes in your previous evaluation.
Gratitude and confidentiality will of course be continued.

\closing
Sincerely yours,
Robert W.~Floyd 

\annotations
RWF/rfn
\smallskip
Enclosures
%\smallskip
%cc: Matthew Kahn
%\smallskip
%\ps
%P.S.: whatever you wish to say here

\endletter

\makelabel
\end

Programs Are Random Walks Are Programs

Robert W. Floyd

6 November 1986, 12:30 PM

To determine moments and other expected values of variables resulting
from random walks or from programs with pseudorandom components, a
certain systematic method seems effective:

   * Introduce explicit variables to track all parameters of interest.
   * By operator strength reduction (e.g., finite difference) methods,
     semilinearize the computational steps.
   * Introduce explicit deterministic variables that track expected values
     of the random ones by linear recurrence.  A well known theorem about
     conditional expected values is useful.
   * Find invariants of the resulting program and solve for final values.
     Typically, this entails finding eigenvectors of a triangular linear
     system.

The method has determined several means and variances in coalesced
hashing, and high moments of certain random walks.  It uses no higher
mathematical notions than those mentioned above, and tends to provide
a firm sense of direction to the analysis.


(mailed: kannan%ernie.berkeley.edu)
PUBLISHERS RECEIVING RWF 106 NOTES

Shelly Langman
Senior Acquisitions Editor
Computer Science
CBS Educational & Professional Publishing
383 Madison Avenue
New York, NY 10017		Dear Shelly:

Pamela S. Kirshen
Editor, Computer Science
D. C. Heath and Co.
125 Spring Street
Lexington, MA  02173		Dear Miss Kirshen:

Richard J. Bonacci
Computer Science Editor
John Wiley & Sons, Inc. Publishers
605 Third Avenue
New York, NY  10158		Dear Dick:

James T. DeWolf
Senior Editor
Computer Science
Addison-Wesley Publishing Co.
Sand Hill Road
Menlo Park, CA  94025		Dear Mr. DeWolf: